#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;


//红黑树实现
// 特点：最长路径不超过最短路径的2倍

//1.节点不是黑就是宏，根节点是黑色
//2.红色节点的孩子只能是黑色。（那么其父亲肯定也是黑色，因没有连续的红色节点）
//3.所有路径黑色节点数量一致
//4.把null当为叶子节点，null节点也是黑（用作判断路径条数）


//重点是2，3。这样就能保证最长路径不超过最短路径的2倍，因为不能连续的红，最短：全黑。最长：一黑一红相间，即黑等于红。就是二倍




enum Color { RED,BLACK};//枚举类型：用数字代表一种颜色，如同用数字代表商品（等同商品价格），方便使用

template <class K,class V>
struct RB_TreeNode
{

	RB_TreeNode* _left;
	RB_TreeNode* _right;
	RB_TreeNode* _parent;
	pair<K, V> _kv;
	Color _col;

	RB_TreeNode(const pair<K,V> kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)//颜色默认用红色，因为根节点是黑色，且插入黑色一定会影响黑节点数量这一规则，插入红色只是可能影响连续红色这一规则
	{}
};


template <class K,class V>
class RB_Tree
{
	typedef RB_TreeNode<K, V> Node;
public:
	//主要学习构成，即insert，删除了解即可，查找简单
	void insert(const pair<K, V> kv)
	{
		//普通搜索二叉树一样插入，接着再判断是否符合红黑树
		Node* cur = _root;
		Node* parent = nullptr;
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
		}
		else
		{
			while (cur)//按搜索树方法寻找，找到是空就插入
			{
				if (kv.first > cur->_kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kv.first < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
					return;//相同先不考虑
			}
			cur = new Node(kv);
			cur->_col = RED;
			cur->_parent = parent;
			if (kv.first > parent->_kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;
		}



		//判断是否符合红黑树,也是从当前插入的cur开始向上排查，连续红就是错
		//红黑树的重点，看叔叔节点的颜色
		//1.叔叔是红色，和parent颜色一样，就可以把grandfather的黑色分到两路，并grandfather变红。这样就能保证两边子树黑节点不变
		//2.叔叔是黑色或者不存在（直线单旋）
		//3.叔叔是黑色或者不存在（折线双旋）
		//2,3的话那么这个局部的左路是两黑（包括根），右路是一黑。保持这个原则进行旋转消除两个红


		while (parent && parent->_col == RED)
		{
			//parent是红色说明上面的节点必然是黑，因为插入之前肯定是红黑树了

			//先分左右子树,用于区分左右旋转
					//弄好亲戚关系
			Node* grandfather = parent->_parent;
			Node* uncle = grandfather->_left;
			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}

			//进入情况
			if (grandfather->_left == parent)
			{
				//情况一
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//叔叔为空，或叔叔存在且为黑
				{
					//情况二：连续左，右单旋
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						
					}
					//情况三：折线，左右双旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}
			else
			{
				//情况一
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//情况二：连续右，左单旋
					if (parent->_right == cur)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//情况三：折线，右左双旋
					else
					{
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}//while
		_root->_col = BLACK;//循环结束，强制写死
	}

	void InOrder()
	{
		InOrder(_root);
		cout << endl;
	}
	int Height()
	{
		return Height(_root);
	}


	vector<vector<int>> levelOrder()
	{
		vector<vector<int>> vv;
		if (_root == nullptr)
			return vv;

		queue<Node*> q;
		int levelSize = 1;
		q.push(_root);

		while (!q.empty())
		{
			// levelSize控制一层一层出
			vector<int> levelV;
			while (levelSize--)
			{
				Node* front = q.front();
				q.pop();
				levelV.push_back(front->_kv.first);
				if (front->_left)
					q.push(front->_left);

				if (front->_right)
					q.push(front->_right);
			}
			vv.push_back(levelV);
			for (auto e : levelV)
			{
				cout << e << " ";
			}
			cout << endl;

			// 上一层出完，下一层就都进队列
			levelSize = q.size();
		}
		return vv;
	}
	bool IsBalanceTree()
	{
		// 检查红黑树几条规则

		Node* pRoot = _root;
		// 空树也是红黑树
		if (nullptr == pRoot)
			return true;

		// 检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}

		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;

			pCur = pCur->_left;
		}

		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}
private:
	Node* _root = nullptr;

	void RotateL(Node* parent)//旋转只关乎父子,1.子树左节点是否为空，2.旋转的parent是否是根(且根无父)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}

	}
	void RotateR(Node* parent)//旋转只关乎父子,1.子树左节点是否为空，2.旋转的parent是否是根（且根无父）
	{
		Node* ppNode = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;

			subL->_parent = ppNode;
		}
	}

	void InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		InOrder(root->_left);
		cout << root->_kv.first <<" ";
		InOrder(root->_right);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int left = Height(root->_left);//先存起来，之后取高的那一个
		int right = Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}
	int _maxHeight(Node* root)
	{
		if (root == nullptr)
			return 0;

		int lh = _maxHeight(root->_left);
		int rh = _maxHeight(root->_right);

		return lh > rh ? lh + 1 : rh + 1;
	}

	int _minHeight(Node* root)
	{
		if (root == nullptr)
			return 0;

		int lh = _minHeight(root->_left);
		int rh = _minHeight(root->_right);

		return lh < rh ? lh + 1 : rh + 1;
	}



	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		//走到null之后，判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}

		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;

		// 检测当前节点与其双亲是否都为红色
		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}

		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}
};

